package _go

/*47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。



示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10*/

var res [][]int

func permuteUnique(nums []int) [][]int {
	res = [][]int{}
	n := len(nums)
	if n == 0 {
		return res
	}
	sort.Ints(nums)
	dfs(nums, map[int]bool{}, []int{})
	return res
}

//nums
//vmap 位置的去重set 判断哪个位置已经用过了 不想1那么简单直接判断这个数用没用过
func dfs(nums []int, vMap map[int]bool, path []int) {
	if len(path) == len(nums) {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		return
	}

	for i := 0; i < len(nums); i++ {
		if vMap[i] {
			continue
		}
		//判断 这个数字之前用没用过
		if i > 0 && nums[i] == nums[i-1] && !vMap[i-1] {
			continue
		}
		path = append(path, nums[i])
		vMap[i] = true
		dfs(nums, vMap, path)
		vMap[i] = false
		path = path[:len(path)-1]
	}
}
